Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Wir haben ja letzte Woche ein Stück weit erstmal die Charakterisierung von Optimallösungen abgeschlossen,

sprich den Satz vom Komplementären Schlupf uns genauer angeguckt und diesbezüglich auch nochmal

den Simplex sozusagen aus einer anderen Sichtweise sozusagen drauf geguckt, nämlich dass die einzelnen Schritte

eigentlich so aussehen, dass wir mit einer primal zulässigen Lösung starten, in dem B-Transschritt

eine duale Lösung y bestimmen und dann überprüfen mit dem Pricing, ob diese zulässig ist.

Und wenn diese zulässig ist, haben wir Optimalität, weil wir während des gesamten Verfahrens den

komplementären Schlupf einhalten. Denn positive XIs können nur in der Basis auftreten und

die erfüllen im Dualen automatisch, so dass wir das Gleichungssystem AB transparent y gleich

CB lösen, automatisch sind damit die Zugesprächung im Dualen mit Gleichheit erfüllt.

Das ist eine andere Sichtweise ein Stück weit auf das Simplex-Verfahren, aber ich denke

durchaus eine interessante, wir werden genau diesen Gedanken nämlich nächste Woche nochmal

aufgreifen, wenn wir das duale Simplex-Verfahren uns angucken, was mit einer dual zulässigen

Lösung y startet, auch die Optimalitätsbedingungen einhält, aber dann versucht primal

zulässig zu werden und das schauen wir uns dann aber nächste Woche noch an, bevor wir

dahin kommen, haben wir ja noch zwei Hausaufgaben, einmal, dass das Simplex-Verfahren überhaupt

terminiert und das zweite, wie fangen wir denn an, wir wissen immer noch nicht, wie

wir zu einer primal zulässigen Basislösung gleich zu Beginn kommen und das steht beides

heute auf dem Programm und gucken wir mal, vielleicht kriegen wir es auch sogar heute

fertig. Gibt es zur letzten Woche und zu dem, was wir dort besprochen haben, noch Nachfragen?

Gut, wenn das nicht der Fall ist, wir hatten ja das letzte Mal schon angefangen, uns zu

überlegen, also was kann denn schiefgehen, sozusagen, an dem Simplex-Verfahren und was

schiefgehen kann, ist das sogenannte Kreiseln, also dass es passieren kann, dass eine Basis

wiederkehrt, eine und dieselbe Basis, wenn das passiert, dann sprechen wir von Kreiseln

und dann würde auch das Simplex-Verfahren tatsächlich in einer Loop-Schleife sein, die

nicht mehr endet. So und wir hatten dann zumindest im Skript, ich habe das nur angedeutet,

wollen wir in der Übung auch nochmal ein Stück weit durchrechnen, es gibt ganz kleine

Beispiele schon mit sechs Variablen, wo das tatsächlich schon auftreten kann, dieses

Phänomen, das ich nicht vorankomme und der Hintergrund dieser Sache ist eigentlich, dass

die zugehörigen Basislösungen degeneriert, also die Basen degeneriert sein müssen, das

heißt, die Basen enthalten Nullkomponenten und bei dem Simplex-Tausch, bei dem Pivotisieren

tauscht man eine Nullkomponente gegen eine andere, man kriegt zwar formal ein anderes

B, aber geometrisch dasselbe X, ja und dieses Phänomen kann sehr einfach auftreten, schon,

wir haben das am Beispiel dieser Pyramide gemacht, wenn mehr als Dimension viele Ungleichungen

einen Punkt bestimmen, dann kann ich praktisch jede beliebige Dimension, viele Kombinationen

aus diesen Anliegen und Ungleichungen auswählen und wir bestimmen alle diesen Punkt. So und

kreiseln ist tatsächlich, und das ist der nächste kleine Satz, das ist der einzige Grund, warum

das Simplex-Verfahren tatsächlich nicht stoppen kann und das liegt einfach daran, dass es

nur endlich viele Basen gibt, weil eine Basis, wenn man uns erinnern, ist ja eine m-elementige

Teilmenge aus einer n-elementigen Teilmenge, also wir nehmen m viele Elemente, also m Spalten

aus den n vielen Variablen, das heißt, wir haben potentiell an verschiedenen Basen, gibt

es nur n über m und damit, wenn eine Basis nicht sich wiederholt, dann muss das Verfahren

offensichtlich enden und das ist als kleine Bemerkung oder als kleiner Satz sozusagen

in 14.3 formuliert, wenn das Simplex-Verfahren nicht terminiert, kreiselt es. Beweis,

es existieren maximal n über m verschiedene Basen. So wie können wir noch sichergehen,

dass er nicht kreiselt, wir können dann sichergehen, wenn dieser degenerierte Fall nicht auftritt,

wenn alle Basis-Variablen echt einen positiven Eintrag haben, also wenn der Support des Lösungsvektors

tatsächlich das B ist, dann wissen wir, dass wir jedes Mal einen Fortschritt machen, dann

ist das Gamma immer größer 0 und dann wandern wir tatsächlich von Ecke zu Ecke und bleiben

nicht an derselben Ecke hängen und das ist auch sozusagen ein einfacher Fall, den wir